The use of data in digital form for all purposes is common throughout the world. Much of this digital data requires a guarantee of the data fidelity. This guarantee means that it would be difficult, or impossible for an unauthorized person to modify the information without detection. Thus, the many kinds of data collected with digital sensors often require validation. Validation provides a secure means for assuring that the data have not been corrupted or modified since their creation.
Commonly used validation methods that leave the data intact are a checksum, a digital signature, or encryption. Discussion of these methods can be found in the book by B. Schneier, Applied Cryptography Protocols, Algorithms, and Source Code in C, J. Wiley & Sons, New York, N.Y., 1994. This reference is incorporated herein by reference.
A checksum guarantees the validity of the data insecurely, because an unauthorized person can modify the data, calculate, and append a new checksum value. The checksum value can be encrypted for greater security. Digital signatures ensure that the data are valid, but the signature is unable to provide an indication of the location and extent of any modifications in the original data. Further, any corruption of the checksum or digital signature value itself gives a false indication of data modification.
One encryption method for authenticating data is based on a message authentication code (MAC), a key shared between the parties. M. Bellare, R. Canetti, and H. Krawczyk presented this method in "The HMAC Construction," RSA Laboratories' CryptoBytes, 2, no. 1, 12 (1996). However, encryption renders data unusable to all persons except the authorized users. Encrypted data are unrecognizable as meaningful information and the data are of no use if the validation (decryption) cannot be performed. Encrypted data suffering corruption or modification in the process of storage and retrieval, or in transmission through a communication channel is therefore rendered generally unusable even for an authorized person. Moreover, in certain situations, encryption methods are unacceptable for use because they conceal the data content.
Methods that hide validation information within the data being authenticated offer an alternative means to validate digital data. Digital watermarks can be added to data by methods falling generally into the field of steganography. Steganographic methods are reviewed by W. Bender, D. Gruhl, and N. Morimoto in "Techniques for Data Hiding," Proc. SPIE, Storage and Retrieval for Image and Video Databases III, 9-10 Feb., 1995, San Jose, Calif. This reference also is incorporated herein by reference.
One method of impressing a digital watermark is given by G. Caronni, in "Assuring Ownership Rights for Digital Images," Proc. Reliable IT Systems, VIS '95, 1995, edited by H. H. Bruggemann and W. Gerhardt-Hackl (Vieweg Publ. Co.: Germany). Another method is given by I. J. Cox, J. Kilian, T. Leighton, and T. Shamoon in "Secure Spread Spectrum Watermarking for Multimedia," NEC Research Inst. Tech. Report 95-10, 1995. These references also are incorporated herein by reference.
Unlike the checksum or digital signature that calculate a measure of the original data, digital watermarking techniques modify the data in order to encode a known signature that can be recovered. The presence of the hidden signature in received data verifies that the data are unchanged, or its absence reveals that the data were modified from the watermarked form. The method of Cox et al (1995) supra is designed specifically for digital images, and it is sufficiently robust to survive even transformations of the digital data to analog form. However, all the above methods proposed for digital watermarking generally detect modifications by means of an external signature, i.e., no metric that measures the fidelity of the original digital data is used. Consequently, there exists no ability to measure in any detail the extent of the changes made or to estimate the precision of the received data. The steganographic watermarking methods differ from the digital signature and checksum methods primarily by being invisible, and by using the digital data to convey the watermark, thus eliminating the need for an appended value.
A robust, new method for validating digital data is taught by the present invention. Information needed to verify digital data is conveyed in the nearly adiabatic modifications to the digital data. The modifications consist of manipulation the digital data in a manner similar to the disclosures in copending U.S. patent application Ser. No. 08/392,642, filed Feb. 23, 1995, for DATA EMBEDDING.
Data validation as disclosed in the present invention hides data-metric quantities in the host digital data that measure the fidelity of the digital data. The data-metric values are incorporated into the data set by means of the data embedding method as disclosed in the above described copending application.
It is therefore an object of the present invention to provide apparatus and method for validating the data in a digital information stream without significantly changing the digital information.
It is another object of the present invention to provide apparatus and method for thwarting unauthorized access to the validation information that is embedded in normal digital data.
It is another object of the present invention to provide apparatus and method for constructing data-metrics from the digital data and a digital key, the data-metrics being constructed to convey the information necessary to verify the authentication of the digital data either completely, or in part.
Additional objects, advantages and novel features of the invention will be set forth in part in the description which follows, and in part will become apparent to those skilled in the art upon examination of the following or may be learned by practice of the invention. The objects and advantages of the invention may be realized and attained by means of the instrumentalities and combinations particularly pointed out in the appended claims.